1. Technical Field
The present invention relates to tree matching algorithms, and more particularly, to a system and method for path-based tree matching for use with medical image processing applications.
2. Discussion of the Related Art
Tree matching algorithms have numerous applications in medical imaging including, inter alia, registration, anatomic labeling, segmentation, and navigation of structures such as vessels and airway trees.
In particular, tree matching algorithms can be used for the following purposes in lung imaging: airway-airway/artery-artery tree matching in images of the same patient taken at different times; airway-airway/artery-artery tree matching from different patients; airway-airway/artery-artery tree matching from a patient to an atlas to perform anatomic labeling; airway-artery matching within an image to determine correspondence between the two tree structures or to assist in detecting additional airways or arteries or for bronchoscopic navigation; and matching of veins to an atlas or to images of the same patient taken at different times.
Airway-airway and artery-artery matching within the same patient at different times can provide an important basis for image registration and automated quantitative analysis. For example, such matching enables automatic change measurement in bronchial wall thickness over time to monitor disease progression or response to treatment. Matching to an atlas can also ease several tasks for a radiologist. An example of this is described in K. Mori, J.-I. Hasegawa, “Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System”, IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, February 2000, and H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt, “Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images”, Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, September 2002.
Atlas matching can be used to determine an anatomic name associated with a problem area identified on a radiologist's report. Matching with different patients allows for large-scale comparisons of the patient's data. Airway-artery matching within the same patient can be used for bronchoscopic navigation. Examples of this are described in B. Geiger, A. P. Kiraly, D. P. Naidich, C. L. Novak, “Virtual Bronchoscopy of Peripheral Nodules using Arteries as Surrogate Pathways”, SPIE Physiology, Function, and Structure From Medical Images, Vol. 5746, 2005, B. Geiger, A. P. Kiraly, D. P. Naidich, C. L. Novak, “System and Method for Endoscopic Path Planning”, U.S. Patent Application Publication No. 20050107679. Airway-artery matching within the same patient can also be used as a basis for improved artery or airway segmentation. An example of this is described in T. Buelow, R. Wiemker, T. Blaffert, C. Lorenz, S. Renisch, “Automatic Extraction of the Pulmonary Artery Tree from Multi-Slice CT Data”, SPIE Physiology, Function, and Structure From Medical Images, pp. 730-740, Vol. 5746, 2005.
Tree matching algorithms require tree structures as input. This structure describes the tree as a series of branches interconnected through branch points. Several known algorithms can be used to obtain the tree structure including, inter alia, tracking, segmentation, and skeletonization. An example of this is described in A. P. Kiraly, J. P. Helferty, E. A. Hoffman, G. McLennan, and W. E. Higgins “3D Path Planning for Virtual Bronchoscopy”, IEEE Trans. on Medical Imaging, pp. 1365-1379, Vol. 23, November 2004. Once the tree structure is obtained, the matching algorithm operates directly on the structure and any data contained therein. Any non-looping tree structure such as airways, arteries, and veins, contains an inherent hierarchy of parent and child branches. Such a tree can be viewed as a directed and branching graph.
There are several approaches to matching airway-airway trees from the same patient. Exemplary approaches are described in C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni, “Trackin 3-D Pulmonary Tree Structures”, Mathematical Methods in Biomedical Image Analysis, pp. 160-169, 1996, and J. Tschirren, K. Palagyi, J. M. Reinhardt, E. A. Hoffman, and M. Sonka, “Segmentation, Skeletonization, and Branchpoint Matching—A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees”, SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031, 2003.
In addition, there are several approaches for providing automated anatomical labeling of the bronchial tree. Examples of these approaches are described in K. Mori, J.-I. Hasegawa, “Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System”, IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, February 2000 and H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt, “Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images”, Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp.1-11, September 2002.
Recent algorithms generally combine a set of features within bifurcation points. Examples of these algorithms are described in C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni, “Tracking 3-D Pulmonary Tree Structures”, Mathematical Methods in Biomedical Image Analysis, pp. 160-169, 1996, J. Tschirren, K. Palagyi, J. M. Reinhardt, E. A. Hoffman, and M. Sonka, “Segmentation, Skeletonization, and Branchpoint Matching—A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees” SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031, 2003, A. C. M. Dumay, R. v.d. Geest, J. J. Gerbrands, E. Jansen, Johan H. C. Reiber, “Consistent Inexact Graph Matching Applied to Labelling Coronary Segments in Arteriograms”, Proc. 11th IAPR, pp. 439-446, Vol. III, 1992, and K. Haris, S. N. Efstratiadis, N. Maglaveras, C. Pappas, J. Gourassas, G. Louridas, “Model-based Morphological Segmentation and Labeling of Coronary Angiograms”, IEEE Trans. on Medical Imaging, pp. 1003-1015, Vol 18, October 1999.
These algorithms also use a general graph matching method such as one that finds a maximal clique in an associated graph. Examples of this are described in M. Pelillo, K. Siddiqi, S. W. Zucker, “Matching Hierarchical Structures Using Association Graphs”, IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1105-1120, Vol. 21, November 1999, and H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt, “Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images”, Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, September 2002. These algorithms may also perform graph matching by relaxing fuzzy assignments. An example of this is described in S. Medasani, R. Krishnapuram, Y. S. Choi, “Graph Matching by Relaxation of Fuzzy Assignments”, IEEE Trans. on Fuzzy Systems, pp. 173-182, Vol. 9, February 2001.
The above-mentioned tree matching algorithms rely on graph matching techniques and focus on a single application. Although graph matching techniques have a firm theoretical background, they may not be the best choice for real-world medical applications where false or missing branches and differences, and changes in anatomy can occur. Further, prior matching methods exploit the hierarchical structure of a tree to match at a branch-to-branch level. Since these methods view the tree structure as a series of nodes with features computed from the branch data, false branches can reduce the effectiveness of these methods. In addition, some of these methods require a matched starting point for each tree structure, making them useless if this information is not available. This requirement also makes it necessary to perform a preliminary registration of the trees for more accurate results. Further, many prior methods require tree structures that need to be manually generated or edited to avoid these limitations.